Levenshtein Distance
Levenshtein Distance
개요
레벤슈타인 거리(Levenshtein Distance)는 두 문자열 간의 유사도를 측정하는 데 사용되는 편집 거리(Edit Distance)의 한 형태로, 한 문자열을 다른 문자열로 변환하는 데 필요한 최소한의 편집 연산 횟수를 나타냅니다. 이 개념은 러시아 수학자 블라디미르 레벤슈타인(Vladimir Levenshtein)이 1965년에 제안하여 그의 이름을 따 명명되었습니다.
레벤슈타인 거리는 자연어처리(NLP), 철자 오류 정정, DNA 서열 분석, 음성 인식, 검색 엔진의 오타 보정 등 다양한 분야에서 핵심적인 역할을 합니다. 특히 철자 오류 정정(Spelling Correction) 시스템에서, 사용자가 입력한 단어와 사전에 등록된 단어 간의 거리를 계산하여 가장 유사한 올바른 단어를 추천하는 데 널리 활용됩니다.
정의와 기본 연산
레벤슈타인 거리는 다음 세 가지 기본적인 편집 연산을 사용하여 계산됩니다:
각 연산은 일반적으로 비용 1을 가지며, 두 문자열 간의 레벤슈타인 거리는 이 연산들을 조합하여 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 비용의 합으로 정의됩니다.
예시
다음 두 단어를 비교해 봅시다:
kitten→sitting
변환 과정:
k→s(치환, 1)e→i(치환, 1)s삽입 (삽입, 1)
총 3회의 연산이 필요하므로, kitten과 sitting의 레벤슈타인 거리는 3입니다.
알고리즘 구현
레벤슈타인 거리는 동적 프로그래밍(Dynamic Programming)을 사용하여 효율적으로 계산할 수 있습니다. 두 문자열 A와 B의 길이를 각각 m과 n이라고 할 때, (m+1) × (n+1) 크기의 2차원 배열 dp를 생성하여 점진적으로 거리를 계산합니다.
의사코드
def levenshtein_distance(A, B):
m, n = len(A), len(B)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if A[i-1] == B[j-1]:
cost = 0
else:
cost = 1
dp[i][j] = min(
dp[i-1][j] + 1, # 삭제
dp[i][j-1] + 1, # 삽입
dp[i-1][j-1] + cost # 치환
)
return dp[m][n]
시간 및 공간 복잡도
- 시간 복잡도: O(m × n)
- 공간 복잡도: O(m × n)
(공간 최적화를 통해 O(min(m, n))로 줄일 수 있음)
응용 분야
1. 철자 오류 정정 (Spelling Correction)
사용자가 acress를 입력했을 때, 사전에 있는 단어 actress, across, access 등과의 레벤슈타인 거리를 계산하여 가장 가까운 단어를 추천합니다. 예를 들어:
| 후보 단어 | 거리 |
|---|---|
| actress | 1 |
| across | 2 |
| access | 2 |
이 경우 actress가 거리가 가장 짧으므로 정정 후보로 제시됩니다.
2. 자연어처리 (NLP)
- 음성 인식 결과의 오류 보정
- 기계 번역 시 입력 오류 처리
- 챗봇에서의 사용자 입력 정규화
3. 생물정보학
DNA 또는 단백질 서열 간의 유사도 분석에 사용되며, 유전자 변이를 추적하는 데 활용됩니다.
4. 검색 엔진
구글, 네이버 등의 검색 엔진은 사용자의 오타를 자동으로 감지하고 "이것을 찾으셨나요?" 형식으로 제안합니다. 이는 내부적으로 레벤슈타인 거리 기반 알고리즘이 작동합니다.
변형 및 확장
레벤슈타인 거리는 다양한 방식으로 확장되어 사용됩니다:
- 가중 레벤슈타인 거리: 특정 연산(예: 자음 치환)에 더 높은 비용을 부여
- 다마레우-레벤슈타인 거리(Damerau-Levenshtein): 문자 교환(transposition) 연산 추가 (예:
hte→the) - 지배적 거리(Dominant Edit Distance): 특정 언어의 오류 패턴을 반영한 가중치 적용
참고 자료 및 관련 문서
- Levenshtein, V. I. (1966). "Binary codes capable of correcting deletions, insertions, and reversals"
- Wikipedia: Levenshtein Distance
- 관련 알고리즘:
- Jaro-Winkler 거리
- Hamming 거리
- Cosine 유사도
레벤슈타인 거리는 단순한 개념이지만, 실세계 응용에서 강력한 도구로 자리 잡고 있으며, 자연어처리 시스템의 정확도와 사용자 경험을 향상시키는 데 핵심적인 역할을 하고 있습니다.
이 문서는 AI 모델(qwen-3-235b-a22b-instruct-2507)에 의해 생성된 콘텐츠입니다.
주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.